package com.zhz.leetcode;

/**
 * 45. 跳跃游戏 II
 * 给你一个非负整数数组nums ，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * 假设你总是可以到达数组的最后一个位置。
 * <p>
 * 示例 1:
 * 输入: nums = [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。
 * 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
 * <p>
 * 示例 2:
 * 输入: nums = [2,3,0,1,4]
 * 输出: 2
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game-ii
 */
public class JumpGameII45 {

    public static void main(String[] args) {
        JumpGameII45 m = new JumpGameII45();
        int[] nums = {3, 2, 1,1,0};
        int step = m.jump(nums);
        System.out.println("最小步数: " + step);
    }

    public int jump1(int[] nums) {
        if (nums == null || nums.length == 1 || nums[0] == 0) {
            return 0;
        }
        int step = 0;
        int index = 0;
        while (index < nums.length - 1) {
            int tmpMax = 0;
            int tmpIndex = index;
            if (tmpIndex + nums[tmpIndex] < nums.length - 1) {
                for (int i = tmpIndex + 1; i < nums.length && i <= tmpIndex + nums[tmpIndex]; i++) {
                    if (tmpMax <= nums[i] + i) {
                        tmpMax = nums[i] + i;
                        index = i;
                    }
                }
            } else {
                index = index + nums[index];
            }
            step++;
        }
        return step;
    }

    /**
     * 官方解法
     * 使用贪心算法，迭代计算最大值
     * 例如[2,3,1,2,4,2,3]
     * <p>
     * 迭代开始:
     * i = 0 时:
     * maxIndex = i + nums[i] = 0+2 = 2 表示可以走的最大距离，接着保存这个值到EndIndex里面去
     * endIndex = maxIndex = 2
     * 步数+1
     * 然后接着遍历
     * <p>
     * i = 1 时
     * maxIndex = Math.max(maxIndex, 1 + 3) = 4
     * 但是因为此时还没有到能走到的最远距离，于是继续往下走
     * <p>
     * i = 2 时
     * maxIndex = Math.max(maxIndex, 2 + 1) = 4 ，maxIndex还是为 4
     * 此时到达第一次记录的最远距离，也就是 i = endIndex = 2,于是记录接下来能到达的最远距离
     * endIndex = maxIndex = 4
     * 于是步数+1
     * <p>
     * i = 3 时
     * maxIndex = Math.max(maxIndex, 3 + 2) = 5 ，maxIndex赋值为5
     * 因为还没有达到 endIndex 也就是 i=4的位置，于是继续往下遍历
     * <p>
     * i = 4 时
     * maxIndex = Math.max(maxIndex, 4 + 4) = 8 ，maxIndex赋值为8
     * 此时到达endIndex 也就是 i=4的位置，此时将最大值赋值给endIndex,也就是接下来能走到的最远index是8
     * 步数+1
     * 继续往下遍历
     * <p>
     * i = 5 时
     * maxIndex = Math.max(maxIndex, 5 + 2) = 8 ，maxIndex还是8
     * 因为还没有达到能走到的最远的位置，也就是endIndex值，于是继续往下遍历
     * <p>
     * 此时到这边就遍历结束了，我们已经到达倒数第二个元素了，不需要在往下遍历了
     * 为什么呢？
     * 因为到达倒数第二个的时候有两种情况，
     * <p>
     * 一种是刚好上次一的最远能走的是到这边，如果是这种情况，那么此时我们的 (endIndex == i)就是等于true，于是step就会加 1，
     * 相当于我们在往前走一步，到达重点。
     * <p>
     * 还有一种情况是，我们当前能到达的最远距离是大于等于数组的长度，那么我们就可以直接结束遍历了
     */
    public int jump(int[] nums) {
        int step = 0;//跳跃次数
        int maxIndex = 0; //目前能跳到的最远位置
        int endIndex = 0; //用于记录之前计算的能走到的最远距离，也就是上次跳跃可达范围右边界（下次的最右起跳点）
        for (int i = 0; i < nums.length - 1; i++) {
            //计算最大值，但是只在到达边界时才赋值给endIndex
            maxIndex = Math.max(maxIndex, i + nums[i]);
            //迭代到上次记录的能到达的最远的距离时，才进行步数加1
            if (endIndex == i) {
                endIndex = maxIndex; // 目前能跳到的最远位置变成了下次起跳位置的有边界
                step++;
            }
        }
        return step;

    }


}
